{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #交错字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isInterleave"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #交错字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定三个字符串&nbsp;<code>s1</code>、<code>s2</code>、<code>s3</code>，请判断&nbsp;<code>s3</code>&nbsp;能不能由&nbsp;<code>s1</code>&nbsp;和&nbsp;<code>s2</code><em>&nbsp;</em><strong>交织（交错）</strong>&nbsp;组成。</p>\n",
    "\n",
    "<p>两个字符串 <code>s</code> 和 <code>t</code> <strong>交织</strong>&nbsp;的定义与过程如下，其中每个字符串都会被分割成若干 <strong>非空</strong> 子字符串：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>s = s<sub>1</sub> + s<sub>2</sub> + ... + s<sub>n</sub></code></li>\n",
    "\t<li><code>t = t<sub>1</sub> + t<sub>2</sub> + ... + t<sub>m</sub></code></li>\n",
    "\t<li><code>|n - m| &lt;= 1</code></li>\n",
    "\t<li><b>交织</b> 是 <code>s<sub>1</sub> + t<sub>1</sub> + s<sub>2</sub> + t<sub>2</sub> + s<sub>3</sub> + t<sub>3</sub> + ...</code> 或者 <code>t<sub>1</sub> + s<sub>1</sub> + t<sub>2</sub> + s<sub>2</sub> + t<sub>3</sub> + s<sub>3</sub> + ...</code></li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>提示：</strong><code>a + b</code> 意味着字符串 <code>a</code> 和 <code>b</code> 连接。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/02/interleave.jpg\" style=\"width: 561px; height: 203px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = &quot;aabcc&quot;, s2 = &quot;dbbca&quot;, s3 = &quot;aadbbcbcac&quot;\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = &quot;aabcc&quot;, s2 = &quot;dbbca&quot;, s3 = &quot;aadbbbaccc&quot;\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = &quot;&quot;, s2 = &quot;&quot;, s3 = &quot;&quot;\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= s1.length, s2.length &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= s3.length &lt;= 200</code></li>\n",
    "\t<li><code>s1</code>、<code>s2</code>、和 <code>s3</code> 都由小写英文字母组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 97&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/interleaving-string/\">https://leetcode-cn.com/problems/interleaving-string/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [IY6buf](https://leetcode.cn/problems/IY6buf/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [IY6buf](https://leetcode.cn/problems/IY6buf/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aabcc\"\\n\"dbbca\"\\n\"aadbbcbcac\"', '\"aabcc\"\\n\"dbbca\"\\n\"aadbbbaccc\"', '\"\"\\n\"\"\\n\"\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        if len(s1)+len(s2)!=len(s3):\n",
    "            return False\n",
    "        n,m = len(s1),len(s2)\n",
    "        dp = [False]*(m+1) \n",
    "        dp[0] = True\n",
    "           \n",
    "        for i in range(1,m+1):\n",
    "            if s3[i-1]!=s2[i-1]:\n",
    "                break\n",
    "            dp[i] = True\n",
    "        for i in range(1,n+1):\n",
    "            dp[0] = (s3[i-1]==s1[i-1] and dp[0])\n",
    "            for j in range(1,m+1):                \n",
    "                dp[j] = (dp[j] and s1[i-1] == s3[i+j-1]) or (dp[j-1] and s2[j-1] == s3[i+j-1])\n",
    "        return dp[m]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1,n2 = len(s1),len(s2)\n",
    "        n = len(s3)\n",
    "        if n1 + n2 != n:\n",
    "            return False\n",
    "        dp = [[False]*(n2 + 1) for _ in range(n1 + 1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(n1+1):\n",
    "            for j in range(n2+1):\n",
    "                p = i + j -1\n",
    "                if i > 0:\n",
    "                    dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[p]) or dp[i][j]\n",
    "                if j > 0:\n",
    "                    dp[i][j] = (dp[i][j-1] and s2[j-1] == s3[p]) or dp[i][j]\n",
    "        return dp[n1][n2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n, m, t = len(s1), len(s2), len(s3)\n",
    "\n",
    "        if n + m != t: return False\n",
    "        \n",
    "        dp = [False] * (m + 1)\n",
    "        dp[0] = True\n",
    "\n",
    "        for i in range(n + 1):\n",
    "            for j in range(m + 1):\n",
    "                p = i + j - 1\n",
    "                if i: dp[j] &= s1[i - 1] == s3[p]\n",
    "                if j: dp[j] |= dp[j - 1] and s2[j - 1] == s3[p]\n",
    "        \n",
    "        return dp[m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        m, n = len(s1), len(s2)\n",
    "        if m + n != len(s3):\n",
    "            return False\n",
    "        dp = [[False for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(0, m + 1):\n",
    "            for j in range(0, n + 1):\n",
    "                if i > 0:\n",
    "                    if dp[i-1][j] and s1[i-1] == s3[i + j - 1]:\n",
    "                        dp[i][j] = True\n",
    "                if j > 0:\n",
    "                    if dp[i][j-1] and s2[j-1] == s3[i + j - 1]:\n",
    "                        dp[i][j] = True\n",
    "        return dp[m][n]\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "#         l1 = len(s1)\n",
    "#         l2 = len(s2)\n",
    "#         l3 = len(s3)\n",
    "#         if l1+l2!=l3:\n",
    "#             return False\n",
    "\n",
    "#         dp = [[False for _ in range(l2+1)] for _ in range(l1+1)]\n",
    "\n",
    "#         dp[0][0]=True\n",
    "#         for i in range(1, l1+1):\n",
    "#             if s1[i-1]==s3[i-1]:\n",
    "#                 dp[i][0]==dp[i-1][0]\n",
    "#         for j in range(1, l2+1):\n",
    "#             if s2[j-1]==s3[j-1]:\n",
    "#                 dp[0][j]==dp[0][j-1]\n",
    "        \n",
    "#         for i in range(1, l1+1):\n",
    "#             for j in range(1,l2+1):\n",
    "#                 dp[i][j]=dp[i][j] or (s1[i-1]==s3[i+j-1] and dp[i-1][j])\n",
    "#                 dp[i][j]=dp[i][j] or (s2[j-1]==s3[i+j-1] and dp[i][j-1])\n",
    "        \n",
    "#         return dp[l1][l2]\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        l1 = len(s1)\n",
    "        l2 = len(s2)\n",
    "        l3 = len(s3)\n",
    "        if l1+l2 !=l3:\n",
    "            return False\n",
    "        \n",
    "        dp = [[False]*(l2+1) for _ in range(l1+1)]   # dp[i][j] 表示 s1[:i]和s2[:j]是否可以交错组成s3[:i+j]\n",
    "        dp[0][0] = True\n",
    "        for i in range(l1+1):\n",
    "            for j in range(l2+1):\n",
    "                if i > 0:\n",
    "                    dp[i][j] = dp[i][j] or (dp[i-1][j] and s1[i-1] == s3[i+j-1])\n",
    "                if j > 0:\n",
    "                    dp[i][j] = dp[i][j] or (dp[i][j-1] and s2[j-1] == s3[i+j-1])\n",
    "        \n",
    "        return dp[l1][l2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        if len(s1)+len(s2)!=len(s3):return False\n",
    "        dp = [[False] * (len(s1)+1) for _ in range(len(s2)+1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, len(s1)+1):\n",
    "            if dp[0][i-1] and s1[i-1]==s3[i-1]:dp[0][i]=True\n",
    "        for i in range(1, len(s2)+1):\n",
    "            if dp[i-1][0] and s2[i-1]==s3[i-1]:dp[i][0]=True\n",
    "        for i in range(2, len(s3)+1):\n",
    "            for index1 in range(1, i):\n",
    "                index2 = i - index1\n",
    "                if index1 > len(s1) or index2>len(s2):continue\n",
    "                # if (s1[index1-1] == s3[i-1] or s2[index2-1] == s3[i-1]) and (dp[index2][index1-1] or dp[index2-1][index1]):dp[index2][index1] = True\n",
    "                if (s1[index1-1] == s3[i-1] and dp[index2][index1-1]) or (s2[index2-1] == s3[i-1] and dp[index2-1][index1]):dp[index2][index1] = True\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1, n2, n3 = len(s1), len(s2), len(s3)\n",
    "\n",
    "        if n1 + n2 != n3: \n",
    "            return False\n",
    "\n",
    "        dp = [[False] * (n2 + 1) for _ in range(n1 + 1)]\n",
    "\n",
    "        dp[0][0] = True\n",
    "\n",
    "        # 赋初值，第一列表示当s2为空时s1与s3是否匹配\n",
    "\n",
    "        for i in range(1, n1 + 1):\n",
    "\n",
    "            if s1[i - 1] == s3[i - 1]:\n",
    "\n",
    "                dp[i][0] = dp[i - 1][0]\n",
    "\n",
    "        # 赋初值，第一排表示当s1为空时s2与s3是否匹配\n",
    "\n",
    "        for j in range(1, n2 + 1):\n",
    "\n",
    "            if s2[j - 1] ==s3[j - 1]:\n",
    "\n",
    "                dp[0][j] = dp[0][j - 1]\n",
    "\n",
    "        for i in range(1, n1 + 1):\n",
    "\n",
    "            for j in range(1, n2 + 1):\n",
    "\n",
    "                if s1[i - 1] == s2[j - 1] == s3[i + j - 1]:\n",
    "\n",
    "                    dp[i][j] = (dp[i - 1][j] | dp[i][j - 1])\n",
    "\n",
    "                elif s1[i - 1] == s3[i + j - 1]:\n",
    "\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "\n",
    "                elif s2[j - 1] == s3[i + j - 1]:\n",
    "\n",
    "                    dp[i][j] = dp[i][j - 1]\n",
    "\n",
    "        return dp[n1][n2]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # s1_n = len(s1)\n",
    "        # s2_n = len(s2)\n",
    "        # s3_n = len(s3)\n",
    "        # if s1_n+s2_n !=s3_n:\n",
    "        #     print(\"s1_n+s2_n !=s3_n\")\n",
    "        #     return False\n",
    "        # if s1_n ==0:\n",
    "        #     return s2 ==s3\n",
    "        # if s2_n ==0:\n",
    "        #     return s1 ==s3\n",
    "        # #\n",
    "        # s1_p,s2_p,s3_p = 0,0,0\n",
    "        # #\n",
    "        # find_flag = 0\n",
    "        # while s3_p<s3_n:#\n",
    "        #     if s1_p<s1_n and s2_p <s2_n:\n",
    "        #         if s1[s1_p]!=s3[s3_p] and s2[s2_p] != s3[s3_p]:\n",
    "        #             return False\n",
    "        #     elif s1_p<s1_n :\n",
    "        #         if s1[s1_p]!=s3[s3_p]:\n",
    "        #             return False\n",
    "        #     elif s2_p <s2_n:\n",
    "        #         if s2[s2_p] != s3[s3_p]:\n",
    "        #             return False\n",
    "        #     else:\n",
    "        #         return False\n",
    "                \n",
    "        #     if find_flag ==0:\n",
    "        #         if s1_p<s1_n and s3[s3_p] == s1[s1_p]:#控制边界\n",
    "        #             s3_p+=1#匹配成功\n",
    "        #             s1_p+=1\n",
    "        #             find_flag =0\n",
    "        #         else:\n",
    "        #             find_flag=1\n",
    "        #     if find_flag ==1:\n",
    "        #         if s2_p <s2_n and s3[s3_p] == s2[s2_p] :\n",
    "        #             s3_p+=1\n",
    "        #             s2_p+=1\n",
    "        #             find_flag =1\n",
    "        #         else:\n",
    "        #             find_flag = 0\n",
    "        # return True\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n=len(s1)\n",
    "        m=len(s2)\n",
    "        k=len(s3)\n",
    "        if n+m!=k:\n",
    "            return False\n",
    "        dp=[[False]*(m+1) for _ in range(n+1)]\n",
    "        dp[0][0]=True\n",
    "\n",
    "        for i in range(n+1):\n",
    "            for j in range(m+1):\n",
    "                index=i+j-1\n",
    "                if i>0:\n",
    "                    dp[i][j]=dp[i][j] or (s3[index]==s1[i-1] and dp[i-1][j])\n",
    "                if j>0:\n",
    "                    dp[i][j]=dp[i][j] or (s3[index]==s2[j-1] and dp[i][j-1])\n",
    "\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        if len(s3)!=len(s1)+len(s2):\n",
    "            return False\n",
    "        dp0=[True]\n",
    "        dp1=[True]\n",
    "        for i in range(len(s1)):\n",
    "            dp1.append(dp1[-1]&(s1[i]==s3[i]))\n",
    "        for i in range(len(s2)):\n",
    "            dp0.append(dp0[-1]&(s2[i]==s3[i]))\n",
    "        for index1,chr1 in enumerate(s1):\n",
    "            dp=[dp1[index1+1]]\n",
    "            for index2,chr2 in enumerate(s2):\n",
    "                dp.append(dp[-1]&(chr2==s3[index1+index2+1]) or dp0[index2+1]&(chr1==s3[index1+index2+1]))\n",
    "            dp0=dp[:]\n",
    "        return dp0[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1, n2, n3 = len(s1), len(s2), len(s3)\n",
    "        if n1 + n2 != n3: # n1 + n2 必须等于 n3\n",
    "            return False\n",
    "        \n",
    "        dp = [[0 for _ in range(n1+1)] for _ in range(n2+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n1+1):\n",
    "            if dp[0][i-1] and s1[i-1] == s3[i-1]:\n",
    "                dp[0][i] = 1\n",
    "        \n",
    "        for i in range(1,n2+1):\n",
    "            if dp[i-1][0] and s2[i-1] == s3[i-1]:\n",
    "                dp[i][0] = 1\n",
    "\n",
    "        for i in range(1,n2+1):\n",
    "            for j in range(1,n1+1):\n",
    "                n = i + j\n",
    "                # if dp[i-1][j-1] and (s3[n-2:n] == s1[j-1] + s2[i-1] or s3[n-2:n] == s2[i-1] + s1[j-1]):\n",
    "                #     dp[i][j] = 1\n",
    "                if dp[i-1][j] and s3[n-1] == s2[i-1]:\n",
    "                    dp[i][j] = 1\n",
    "                if dp[i][j-1] and s3[n-1] == s1[j-1]:\n",
    "                    dp[i][j] = 1\n",
    "        return dp[n2][n1] == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        dp=[[False for i in range(len(s2)+1)]for i in range(len(s1)+1)]\n",
    "\n",
    "        dp[0][0]=True\n",
    "        if len(s1)+len(s2)!=len(s3):\n",
    "            return False\n",
    "\n",
    "        for i in range(1,len(s1)+1):\n",
    "            dp[i][0]=dp[i-1][0] and s1[i-1]==s3[i-1]\n",
    "        for j in range(1,len(s2)+1):\n",
    "            dp[0][j]=dp[0][j-1] and s2[j-1]==s3[j-1]\n",
    "\n",
    "        for i in range(1,len(s1)+1):\n",
    "            for j in range(1,len(s2)+1):\n",
    "                dp[i][j]=(dp[i-1][j] and s1[i-1]==s3[i+j-1]) or (dp[i][j-1] and s2[j-1]==s3[i+j-1])\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        m, n, t = len(s1), len(s2), len(s3)\n",
    "        \n",
    "        # Length check\n",
    "        if m + n != t:\n",
    "            return False\n",
    "        \n",
    "        # Initialize dp array\n",
    "        dp = [[False] * (n + 1) for _ in range(m + 1)]\n",
    "        dp[0][0] = True\n",
    "        \n",
    "        # Initialize the first row\n",
    "        for j in range(1, n + 1):\n",
    "            dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]\n",
    "        \n",
    "        # Initialize the first column\n",
    "        for i in range(1, m + 1):\n",
    "            dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]\n",
    "        \n",
    "        # DP transition\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or \\\n",
    "                           (dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])\n",
    "        \n",
    "        return dp[m][n]\n",
    "\n",
    "# Test the function\n",
    "sol = Solution()\n",
    "print(sol.isInterleave(\"aabcc\", \"dbbca\", \"aadbbcbcac\"))  # Should return True\n",
    "print(sol.isInterleave(\"aabcc\", \"dbbca\", \"aadbbbaccc\"))  # Should return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        method = 'mine'\n",
    "        if method == 'mine':\n",
    "            m, n, t = len(s1), len(s2), len(s3)\n",
    "            if m + n != t: return False\n",
    "            dp = [[False] * (n + 1) for _ in range(m + 1)]\n",
    "            dp[0][0] = True\n",
    "            for i in range(m + 1):\n",
    "                for j in range(n + 1):\n",
    "                    if i == 0 and j == 0:\n",
    "                        continue\n",
    "                    elif i == 0:\n",
    "                        dp[i][j] = (dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])\n",
    "                    elif j == 0:\n",
    "                        dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i - 1 + j])\n",
    "                    else:\n",
    "                        dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i - 1 + j]) or (dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])\n",
    "            return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        m = len(s1)\n",
    "        n = len(s2)\n",
    "        l = len(s3)\n",
    "        if m + n != l:\n",
    "            return False\n",
    "        dp = [[False] * (n + 1) for _ in range(m + 1)]  # m+1行 n+1列\n",
    "        dp[0][0] = True  # 初始是T，都是空字符串\n",
    "        for i in range(1, m + 1):\n",
    "            if s1[i - 1] == s3[i - 1]:\n",
    "                dp[i][0] = True\n",
    "            else:\n",
    "                break\n",
    "        for j in range(1, n + 1):\n",
    "            if s2[j - 1] == s3[j - 1]:\n",
    "                dp[0][j] = True\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = (dp[i - 1][j] == 1 and s1[i - 1] == s3[i + j - 1]) or \\\n",
    "                       (dp[i][j - 1] == 1 and s2[j - 1] == s3[i + j - 1])\n",
    "        return dp[m][n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        m, n = len(s1) + 1, len(s2) + 1\n",
    "        if m + n - 2 != len(s3): return False\n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "\n",
    "        for i in range(1, m):\n",
    "            dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]\n",
    "        for j in range(1, n):\n",
    "            dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i - 1][j] and s1[i - 1] == s3[i + j - 1] or dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]\n",
    "        \n",
    "\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # m, n = len(s1), len(s2)\n",
    "        # if len(s3) != m + n: return False\n",
    "        # dp = [[False] * (n + 1) for _ in range(m + 1)]\n",
    "        # dp[0][0] = True\n",
    "        # for i in range(1, m + 1):\n",
    "        #     dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]\n",
    "        \n",
    "        # for j in range(1, n + 1):\n",
    "        #     dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]\n",
    "        \n",
    "        # for i in range(1, m + 1):\n",
    "        #     for j in range(1, n + 1):\n",
    "        #         dp[i][j] = dp[i - 1][j] and s1[i - 1] == s3[i + j - 1] or dp[i][j - 1] and s2[ j - 1] == s3[i + j - 1]\n",
    "        \n",
    "        # return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n, m, l = len(s1), len(s2), len(s3)\n",
    "        if n + m != l: return False\n",
    "        dp = [[False] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]\n",
    "        for j in range(1, m + 1):\n",
    "            dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                if s1[i - 1] == s3[i + j - 1]:\n",
    "                    dp[i][j] |= dp[i - 1][j]\n",
    "                if s2[j - 1] == s3[i + j - 1]:\n",
    "                    dp[i][j] |= dp[i][j - 1]\n",
    "        return dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        m,n,t = len(s1), len(s2), len(s3)\n",
    "        if m+n != t:\n",
    "            return False\n",
    "            \n",
    "        dp = [[False for _  in range(n+1)] for _ in range(m+1)]\n",
    "\n",
    "        dp[0][0] = True\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            dp[i][0] = s1[0:i] == s3[0:i] \n",
    "        for j in range(1, n+1):\n",
    "            dp[0][j] = s2[0:j] == s3[0:j]\n",
    "\n",
    "        \n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                \n",
    "                a = (s1[i-1] == s3[i+j-1]) and dp[i-1][j]\n",
    "                b = (s2[j-1] == s3[i+j-1]) and dp[i][j-1]\n",
    "\n",
    "                dp[i][j] = a or b\n",
    "\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1,n2,n3 = len(s1), len(s2), len(s3)\n",
    "        if n1+n2!=n3:\n",
    "            return False\n",
    "        dp = [[False]*(n2+1) for i in range(n1+1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, n1+1):\n",
    "            if s1[i-1] == s3[i-1]:\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "        for i in range(1, n2+1):\n",
    "            if s2[i-1] == s3[i-1]:\n",
    "                dp[0][i] = dp[0][i-1]\n",
    "        for i in range(1, n1 + 1):\n",
    "            for j in range(1, n2 + 1):\n",
    "                if s3[i + j -1] == s1[i-1] == s2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j] | dp[i][j-1]\n",
    "                elif s3[i + j -1] == s1[i-1]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                elif s3[i + j -1] == s2[j-1]:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "        return dp[n1][n2]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1, n2, n3 = len(s1), len(s2), len(s3)\n",
    "        if n1 + n2 != n3:\n",
    "            return False\n",
    "        \n",
    "        dp = [[0 for _ in range(n1+1)] for _ in range(n2+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,n1+1):\n",
    "            if dp[0][i-1] and s1[i-1] == s3[i-1]:\n",
    "                dp[0][i] = 1\n",
    "        \n",
    "        for i in range(1,n2+1):\n",
    "            if dp[i-1][0] and s2[i-1] == s3[i-1]:\n",
    "                dp[i][0] = 1\n",
    "\n",
    "        for i in range(1,n2+1):\n",
    "            for j in range(1,n1+1):\n",
    "                n = i + j\n",
    "                # if dp[i-1][j-1] and (s3[n-2:n] == s1[j-1] + s2[i-1] or s3[n-2:n] == s2[i-1] + s1[j-1]):\n",
    "                #     dp[i][j] = 1\n",
    "                if dp[i-1][j] and s3[n-1] == s2[i-1]:\n",
    "                    dp[i][j] = 1\n",
    "                if dp[i][j-1] and s3[n-1] == s1[j-1]:\n",
    "                    dp[i][j] = 1\n",
    "        return dp[n2][n1] == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n=len(s1)\n",
    "        m=len(s2)\n",
    "        k=len(s3)\n",
    "        if n+m!=k: return False\n",
    "        f=[[False]*(m +1) for _ in range(n+1)]\n",
    "        if(s3==\"\"):return True\n",
    "        f[0][0]=True\n",
    "        for i in range(0,n+1):\n",
    "            for j in range(0,m+1):\n",
    "                if(i>0):\n",
    "                    f[i][j]|=(f[i-1][j] and s3[i+j-1]==s1[i-1])\n",
    "                if(j>0):\n",
    "                    f[i][j]|=(f[i][j-1] and s3[i+j-1]==s2[j-1])\n",
    "        return f[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1,n2,n3 = len(s1),len(s2),len(s3) \n",
    "        if n1+n2!=n3:\n",
    "            return False\n",
    "        dp = [[False]*(n2+1) for _ in range(n1+1)] \n",
    "        dp[0][0] = True \n",
    "\n",
    "        for i in range(n1+1):\n",
    "            for j in range(n2+1):\n",
    "                if i>0 and s1[i-1]==s3[i+j-1]:\n",
    "                    dp[i][j] = dp[i][j] or dp[i-1][j]  \n",
    "                if j>0 and s2[j-1]==s3[i+j-1]:\n",
    "                    dp[i][j] = dp[i][j] or dp[i][j-1] \n",
    "        # print(dp)\n",
    "        return dp[n1][n2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        l1, l2, l3 = len(s1), len(s2), len(s3)\n",
    "        if l1 == 0:\n",
    "            return s2 == s3\n",
    "        if l2 == 0:\n",
    "            return s1 == s3\n",
    "        if l1 + l2 != l3:\n",
    "            return False\n",
    "        f = [[False] * (l2 + 1) for _ in range(l1 + 1)]\n",
    "        f[0][0] = True\n",
    "        for i in range(1, l1 + 1):\n",
    "            f[i][0] = f[i - 1][0] and s3[i - 1] == s1[i - 1]\n",
    "        for j in range(1, l2 + 1):\n",
    "            f[0][j] = f[0][j - 1] and s3[j - 1] == s2[j - 1]\n",
    "        for i in range(1, l1 + 1):\n",
    "            for j in range(1, l2 + 1):\n",
    "                if s3[i + j - 1] == s1[i - 1]:\n",
    "                    f[i][j] = f[i][j] or f[i - 1][j]\n",
    "                if s3[i + j - 1] == s2[j - 1]:\n",
    "                    f[i][j] = f[i][j] or f[i][j - 1]\n",
    "        return f[l1][l2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1, n2, n3 = len(s1), len(s2), len(s3)\n",
    "        if n1 + n2 != n3: return False\n",
    "        dp = [[False] * (n2 + 1) for _ in range(n1 + 1)]\n",
    "        dp[0][0] = True\n",
    "\n",
    "        for i in range(1, n1 + 1):\n",
    "            if s1[i-1] == s3[i-1]:\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "        \n",
    "        for j in range(1, n2 + 1):\n",
    "            if s2[j-1] == s3[j-1]:\n",
    "                dp[0][j] = dp[0][j-1]\n",
    "\n",
    "        for i in range(1, n1 + 1):\n",
    "            for j in range(1, n2 + 1):\n",
    "                if s1[i-1] == s2[j-1] == s3[i+j-1]:\n",
    "                    dp[i][j] = dp[i-1][j] or dp[i][j-1]\n",
    "                elif s1[i-1] == s3[i+j-1]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                elif s2[j-1] == s3[i+j-1]:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "        \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1, n2, n3 = len(s1), len(s2), len(s3)\n",
    "        if n1 + n2 != n3:\n",
    "            return False\n",
    "        dp = [[False] * (n2 + 1) for _ in range(0, n1 + 1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, n1 + 1):\n",
    "            dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]\n",
    "        for j in range(1, n2 + 1):\n",
    "            dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]\n",
    "        for i in range(1, n1 + 1):\n",
    "            for j in range(1, n2 + 1):\n",
    "                dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i + j - 1]) or \\\n",
    "                            (dp[i][j-1] and s2[j-1] == s3[i + j - 1])\n",
    "        return dp[n1][n2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1,n2,n3 = len(s1),len(s2),len(s3)\n",
    "        if n3!=n1+n2:return False\n",
    "        dp = [[False]*(n2+1) for _ in range(n1+1)]\n",
    "        dp[0][0] = True\n",
    "        #第一列表示s2为空的时候s1与s3是否匹配\n",
    "        for i in range(1,n1+1):\n",
    "            if s1[i-1]==s3[i-1]:dp[i][0]=dp[i-1][0]\n",
    "        for j in range(1,n2+1):\n",
    "            if s2[j-1]==s3[j-1]:dp[0][j]=dp[0][j-1]\n",
    "        for i in range(1,n1+1):\n",
    "            for j in range(1,n2+1):\n",
    "                if s1[i-1]==s2[j-1]==s3[i+j-1]: #如果两种都符合，结果取决于以下两种情况的或\n",
    "                    dp[i][j] = dp[i-1][j]|dp[i][j-1]\n",
    "                elif s1[i-1]==s3[i+j-1]: #取决s1[0:i-1]和s2[0:j]能否组成s3[0:i+j-1]\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                elif s2[j-1]==s3[i+j-1]: #取决s1[0:i]和s2[0:j-1]能否组成s3[0:i+j-1]\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                # 如何不匹配的话这里就仍然是False不用进行调整\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        \n",
    "        m = len(s1)\n",
    "        n = len(s2)\n",
    "        if m + n != len(s3):\n",
    "            return False\n",
    "        dp = [[False] * (n+1) for _ in range(0, m+1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(0, m+1):\n",
    "            for j in range(0, n+1):\n",
    "                if i == 0 and j == 0:\n",
    "                    continue\n",
    "                elif i == 0:\n",
    "                    if s2[j-1] == s3[j-1]:\n",
    "                        dp[0][j] = dp[0][j-1]\n",
    "                elif j == 0:\n",
    "                    if s1[i-1] == s3[i-1]:\n",
    "                        dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    if (s1[i-1] == s3[i+j-1] and dp[i-1][j]) or (s2[j-1] == s3[i+j-1] and dp[i][j-1]):\n",
    "                        dp[i][j] = True\n",
    "        return dp[-1][-1]\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        if len(s1)+len(s2)!=len(s3):\n",
    "            return False\n",
    "        n,m = len(s1),len(s2)\n",
    "        dp = [[False]*(m+1) for _ in range(n+1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1,n+1):\n",
    "            if s3[i-1]==s1[i-1]:\n",
    "                dp[i][0] = True\n",
    "            else:\n",
    "                break\n",
    "            \n",
    "           \n",
    "        for i in range(1,m+1):\n",
    "            if s3[i-1]!=s2[i-1]:\n",
    "                break\n",
    "            dp[0][i] = True\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):                \n",
    "                dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])\n",
    "        return dp[n][m]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        # if s1 == \"\":\n",
    "        #     return s2 == s3\n",
    "        # if s2 == \"\":\n",
    "        #     return s1 == s3\n",
    "        # n = min(len(s1),len(s2),len(s3))\n",
    "        # flag = False\n",
    "        # for i in range(1,n+1):\n",
    "        #     if s3[:i] == s1[:i] or s3[:i] == s2[:i]:\n",
    "        #         if s3[:i] == s1[:i]:\n",
    "        #             flag |= self.isInterleave(s1[i:],s2[:],s3[i:])\n",
    "        #         if s3[:i] == s2[:i]:\n",
    "        #             flag |= self.isInterleave(s1[:],s2[i:],s3[i:])\n",
    "        #     else:\n",
    "        #         break\n",
    "        # return flag\n",
    "        m,n,c = len(s1),len(s2),len(s3)\n",
    "        if m+n != c:\n",
    "            return False\n",
    "        demo = [[True]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(1,n+1):\n",
    "            demo[0][i] = s2[:i] == s3[:i]\n",
    "        for i in range(1,m+1):\n",
    "            demo[i][0] = s1[:i] == s3[:i]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                demo[i][j] = (demo[i-1][j] and s1[i-1] == s3[i+j-1]) or \\\n",
    "                (demo[i][j-1] and s2[j-1] == s3[i+j-1])\n",
    "        return demo[m][n]\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        len1, len2 = len(s1), len(s2)\n",
    "        if len1+len2!=len(s3):return False\n",
    "        dp = [[False] * (len1+1) for _ in range(len2+1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, len1+1):\n",
    "            if dp[0][i-1] and s1[i-1]==s3[i-1]:dp[0][i]=True\n",
    "        for i in range(1, len2+1):\n",
    "            if dp[i-1][0] and s2[i-1]==s3[i-1]:dp[i][0]=True\n",
    "        for i in range(2, len(s3)+1):\n",
    "            for index1 in range(1, i):\n",
    "                index2 = i - index1\n",
    "                if index1 > len1 or index2>len2:continue\n",
    "                # if (s1[index1-1] == s3[i-1] or s2[index2-1] == s3[i-1]) and (dp[index2][index1-1] or dp[index2-1][index1]):dp[index2][index1] = True\n",
    "                if (s1[index1-1] == s3[i-1] and dp[index2][index1-1]) or (s2[index2-1] == s3[i-1] and dp[index2-1][index1]):dp[index2][index1] = True\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        if len(s1) + len(s2) != len(s3):    return False\n",
    "        \n",
    "        m, n, k = len(s1), len(s2), len(s3)\n",
    "        dp = [[False] * (n + 1) for _ in range(m + 1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(m):\n",
    "            if s1[i] == s3[i]:  dp[i+1][0] = True\n",
    "            else:   break\n",
    "        \n",
    "        for j in range(n):\n",
    "            if s2[j] ==s3[j]:   dp[0][j+1] = True\n",
    "            else:   break\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = (dp[i][j-1] and s2[j-1] == s3[i + j - 1]) or (dp[i-1][j] and s1[i-1] == s3[i + j - 1])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        len1 = len(s1)\n",
    "        len2 = len(s2)\n",
    "        len3 = len(s3)\n",
    "        if len1 + len2 != len3:\n",
    "            return False\n",
    "        \n",
    "        dp = [[False] * (len2+1) for _ in range(len1+1)]     \n",
    "        dp[0][0] = True\n",
    "\n",
    "        for i in range(len1):\n",
    "            if s1[i] == s3[i] and dp[i][0]:\n",
    "                dp[i+1][0] = True\n",
    "        for j in range(len2):\n",
    "            if s2[j] == s3[j] and dp[0][j]:\n",
    "                dp[0][j+1] = True\n",
    "        for i in range(len1):\n",
    "            for j in range(len2):\n",
    "                ch1 = s1[i]\n",
    "                ch2 = s2[j]\n",
    "                ch3 = s3[i+j+1]\n",
    "                if (ch1 == ch3 and dp[i][j+1]) or (ch2 == ch3 and dp[i+1][j]):\n",
    "                    dp[i+1][j+1] = True\n",
    "        return dp[len1][len2] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        len1, len2 = len(s1), len(s2)\n",
    "        if len1+len2!=len(s3):return False\n",
    "        dp = [[False] * (len1+1) for _ in range(len2+1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, len1+1):\n",
    "            if dp[0][i-1] and s1[i-1]==s3[i-1]:dp[0][i]=True\n",
    "        for i in range(1, len2+1):\n",
    "            if dp[i-1][0] and s2[i-1]==s3[i-1]:dp[i][0]=True\n",
    "        for i in range(2, len(s3)+1):\n",
    "            for index1 in range(1, i):\n",
    "                index2 = i - index1\n",
    "                if index1 > len1 or index2>len2:continue\n",
    "                # if (s1[index1-1] == s3[i-1] or s2[index2-1] == s3[i-1]) and (dp[index2][index1-1] or dp[index2-1][index1]):dp[index2][index1] = True\n",
    "                if (s1[index1-1] == s3[i-1] and dp[index2][index1-1]) or (s2[index2-1] == s3[i-1] and dp[index2-1][index1]):dp[index2][index1] = True\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        m,n = len(s1),len(s2)\n",
    "        if m+n !=len(s3):\n",
    "            return False\n",
    "        f = [[False]*(n+1) for _ in range(m+1)]\n",
    "        f[0][0] = True\n",
    "        for i in range(m+1):\n",
    "            for j in range(n+1):\n",
    "                k = i+j-1\n",
    "                if i and s1[i-1]==s3[k]:\n",
    "                    f[i][j] = f[i-1][j]\n",
    "                if j and s2[j-1]==s3[k]:\n",
    "                    f[i][j] |= f[i][j-1]\n",
    "        return f[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1,n2,n3 = len(s1),len(s2),len(s3)\n",
    "        if n1+n2 != n3 :\n",
    "            return False\n",
    "        dp = [[False]*(n2+1) for _ in range(n1+1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1,n1+1):\n",
    "            if s1[i-1] == s3[i-1]:\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "        for j in range(1,n2+1):\n",
    "            if s2[j-1] == s3[j-1]:\n",
    "                dp[0][j] = dp[0][j-1]\n",
    "        for i in range(1,n1+1):\n",
    "            for j in range(1,n2+1):\n",
    "                if s1[i-1] == s3[i+j-1] and s2[j-1] == s3[i+j-1]:\n",
    "                    dp[i][j] = (dp[i-1][j] or dp[i][j-1])\n",
    "                elif s1[i-1] == s3[i+j-1]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                elif s2[j-1] == s3[i+j-1]:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        if len(s1)+len(s2)!=len(s3):\n",
    "            return False\n",
    "        dp=[[False]*(len(s2)+1) for _ in range(len(s1)+1)]\n",
    "        dp[0][0]=True\n",
    "        for i in range(len(s1)):\n",
    "            dp[i+1][0]=dp[i][0] and s1[i]==s3[i]\n",
    "        for i in range(len(s2)):\n",
    "            dp[0][i+1]=dp[0][i] and s2[i]==s3[i]\n",
    "        for i in range(len(s1)):\n",
    "            for j in range(len(s2)):\n",
    "                if s1[i]==s3[i+j+1] and s1[i]==s2[j]:\n",
    "                    dp[i+1][j+1]=dp[i+1][j] or dp[i][j+1]\n",
    "                elif s1[i]==s3[i+j+1]:\n",
    "                    dp[i+1][j+1]=dp[i][j+1]\n",
    "                elif s2[j]==s3[i+j+1]:\n",
    "                    dp[i+1][j+1]=dp[i+1][j]\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "\n",
    "        len1 = len(s1)\n",
    "        len2 = len(s2)\n",
    "        len3 = len(s3)\n",
    "        if len3!=(len1 + len2):\n",
    "            return False\n",
    "\n",
    "        dp_list = []\n",
    "        for kk in range(len1+1):\n",
    "            dp_list.append([-1]*(len2+1))\n",
    "        dp_list[0][0] = True\n",
    "        for kk in range(1, len1+1):\n",
    "            dp_list[kk][0] = (s1[:kk]==s3[:kk])\n",
    "        for kk in range(1, len2+1):    \n",
    "            dp_list[0][kk] = (s2[:kk]==s3[:kk])\n",
    "\n",
    "        for ii in range(1, len1+1):\n",
    "            for jj in range(1, len2+1):\n",
    "                Cs3 = s3[ii+jj-1]\n",
    "                dp_list[ii][jj] = (dp_list[ii-1][jj] and (s1[ii-1] == Cs3)) or (dp_list[ii][jj-1] and (s2[jj-1] == Cs3))\n",
    "\n",
    "\n",
    "        return dp_list[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        m, n, l = len(s1), len(s2), len(s3)\n",
    "        \n",
    "        if m + n != l:\n",
    "            return False\n",
    "\n",
    "        dp = [ [0] * (n + 1) for _ in range(m + 1)]\n",
    "        dp[0][0] = True\n",
    "        \n",
    "        for i in range(m + 1):\n",
    "            for j in range(n + 1):\n",
    "                p = i + j -1\n",
    "                if i > 0:\n",
    "                    dp[i][j] = dp[i][j] or dp[i - 1][j] and s1[i - 1] == s3[p]\n",
    "                \n",
    "                if j > 0:\n",
    "                    dp[i][j] = dp[i][j] or dp[i][j - 1] and s2[j - 1] == s3[p]\n",
    "\n",
    "        return dp[m][n]\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "\n",
    "        # 那就二叉搜索树+启发式剪枝？\n",
    "        # 2^100有点爆炸了吧\n",
    "\n",
    "        if len(s1) + len(s2) != len(s3):\n",
    "            return False\n",
    "\n",
    "        if len(s3) == 0:\n",
    "            return True\n",
    "\n",
    "        # mark = False\n",
    "        # if len(s1) > 0 and s1[0] == s3[0]:\n",
    "        #     mark = mark or self.isInterleave(s1[1:], s2, s3[1:])\n",
    "        \n",
    "        # if mark:\n",
    "        #     return True\n",
    "        \n",
    "        # if len(s2) >0 and s2[0] == s3[0]:\n",
    "        #     mark = mark or self.isInterleave(s1, s2[1:], s3[1:])\n",
    "        \n",
    "        # return mark\n",
    "\n",
    "        # 超时\n",
    "\n",
    "        # 动归\n",
    "        \n",
    "        res = [[False]*(len(s2)+1) for _ in range((len(s1)+1))]\n",
    "        # i, j 代表长度\n",
    "        for i in range(0, len(s1)+1):\n",
    "            for j in range(0, len(s2)+1):\n",
    "                if i == 0 and j == 0:\n",
    "                    res[i][j] = True\n",
    "                    continue\n",
    "                if i != 0 and s3[i+j-1] == s1[i-1]:\n",
    "                    res[i][j] = res[i][j] or res[i-1][j]\n",
    "                if j != 0 and s3[i+j-1] == s2[j-1]:\n",
    "                    res[i][j] = res[i][j] or res[i][j-1]\n",
    "                \n",
    "                \n",
    "        return bool(res[-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        m,n,l=len(s1),len(s2),len(s3)\n",
    "        if l!=m+n:\n",
    "            return False\n",
    "        dp=[[False]*(n+1) for _ in range(m+1)]\n",
    "        dp[0][0]=True\n",
    "       \n",
    "        for i in range(1,m+1):\n",
    "            if s1[i-1]==s3[i-1]:\n",
    "                dp[i][0]=dp[i-1][0]\n",
    "        for j in range(1,n+1):\n",
    "            if s2[j-1]==s3[j-1]:\n",
    "                dp[0][j]=dp[0][j-1]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if s1[i-1]==s2[j-1]==s3[i+j-1]:\n",
    "                    dp[i][j]=(dp[i-1][j]|dp[i][j-1])\n",
    "                elif s1[i-1]==s3[i+j-1]:\n",
    "                    dp[i][j]=dp[i-1][j]\n",
    "                elif s2[j-1]==s3[i+j-1]:\n",
    "                    dp[i][j]=dp[i][j-1]\n",
    "                #print(dp)\n",
    "        return dp[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        l1,l2=len(s1),len(s2)\n",
    "        if l1+l2 !=len(s3): return False\n",
    "        dp=[[False for i in range(l2+1)] for j in range(l1+1)]\n",
    "        for i in range(l1+1):\n",
    "            for j in range(l2+1):\n",
    "                k=i+j-1\n",
    "                if i==0 and j==0:\n",
    "                    dp[i][j]=True\n",
    "                elif i==0 and j!=0:\n",
    "                    if dp[i][j-1] and s2[j-1]==s3[k]:\n",
    "                        dp[i][j]=True\n",
    "                elif i!=0 and j==0:\n",
    "                    if dp[i-1][j] and s1[i-1]==s3[k]:\n",
    "                        dp[i][j]=True\n",
    "                else:\n",
    "                    if s1[i-1]==s3[k] and dp[i-1][j]:\n",
    "                        dp[i][j]=True\n",
    "                \n",
    "                    if s2[j-1]==s3[k] and dp[i][j-1]:\n",
    "                        dp[i][j]=True\n",
    "           \n",
    "        return dp[l1][l2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        len1, len2 = len(s1), len(s2)\n",
    "        if len1+len2!=len(s3):return False\n",
    "        dp = [[False] * (len1+1) for _ in range(len2+1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, len1+1):\n",
    "            if dp[0][i-1] and s1[i-1]==s3[i-1]:dp[0][i]=True\n",
    "        for i in range(1, len2+1):\n",
    "            if dp[i-1][0] and s2[i-1]==s3[i-1]:dp[i][0]=True\n",
    "        for i in range(2, len(s3)+1):\n",
    "            for index1 in range(1, i):\n",
    "                index2 = i - index1\n",
    "                if index1 > len1 or index2>len2:continue\n",
    "                # if (s1[index1-1] == s3[i-1] or s2[index2-1] == s3[i-1]) and (dp[index2][index1-1] or dp[index2-1][index1]):dp[index2][index1] = True\n",
    "                if (s1[index1-1] == s3[i-1] and dp[index2][index1-1]) or (s2[index2-1] == s3[i-1] and dp[index2-1][index1]):dp[index2][index1] = True\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1,n2 = len(s1), len(s2)\n",
    "        m = len(s3)\n",
    "        if n1+n2 != m:\n",
    "            return False\n",
    "\n",
    "        dp = [[False]*(n2+1) for _ in range(n1+1)]\n",
    "        \n",
    "        for i in range(n1+1):\n",
    "            for j in range(n2+1):\n",
    "                if i+j == 0:\n",
    "                    dp[i][j] = True\n",
    "                elif i == 0:\n",
    "                    dp[i][j] = dp[i][j-1] and s2[j-1]==s3[j-1]\n",
    "                elif j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] and s1[i-1]==s3[i-1]\n",
    "                else:\n",
    "                    dp[i][j] = (dp[i][j-1] and s2[j-1]==s3[i+j-1]) or \\\n",
    "                                (dp[i-1][j] and s1[i-1]==s3[i+j-1])\n",
    "        \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        if len(s1) + len(s2) != len(s3):    return False\n",
    "        \n",
    "        m, n, k = len(s1), len(s2), len(s3)\n",
    "        dp = [[False] * (n + 1) for _ in range(m + 1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(m):\n",
    "            if s1[i] == s3[i]:  dp[i+1][0] = True\n",
    "            else:   break\n",
    "        \n",
    "        for j in range(n):\n",
    "            if s2[j] ==s3[j]:   dp[0][j+1] = True\n",
    "            else:   break\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = (dp[i][j-1] and s2[j-1] == s3[i + j - 1]) or (dp[i-1][j] and s1[i-1] == s3[i + j - 1])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        if len(s1) + len(s2) != len(s3):\n",
    "            return False\n",
    "        dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, len(s1)+1):\n",
    "            if s1[i-1] != s3[i-1]:\n",
    "                break\n",
    "            dp[i][0] = True\n",
    "        for j in range(1, len(s2)+1):\n",
    "            if s2[j-1] != s3[j-1]:\n",
    "                break\n",
    "            dp[0][j] = True\n",
    "        for i in range(1, len(s1)+1):\n",
    "            for j in range(1, len(s2)+1):\n",
    "                if (s1[i-1] == s3[i+j-1] and dp[i-1][j]) or (s2[j-1] == s3[i+j-1] and dp[i][j-1]):\n",
    "                    dp[i][j] = True\n",
    "        return dp[len(s1)][len(s2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1, n2, n3 = len(s1), len(s2), len(s3)\n",
    "        if n1 + n2 != n3: return False\n",
    "        dp = [[False] * (n2 + 1) for _ in range(n1 + 1)]\n",
    "        dp[0][0] = True\n",
    "        # 赋初值，第一列表示当s2为空时s1与s3是否匹配\n",
    "        for i in range(1, n1 + 1):\n",
    "            if s1[i - 1] == s3[i - 1]:\n",
    "                dp[i][0] = dp[i - 1][0]\n",
    "        # 赋初值，第一排表示当s1为空时s2与s3是否匹配\n",
    "        for j in range(1, n2 + 1):\n",
    "            if s2[j - 1] ==s3[j - 1]:\n",
    "                dp[0][j] = dp[0][j - 1]\n",
    "        for i in range(1, n1 + 1):\n",
    "            for j in range(1, n2 + 1):\n",
    "                if s1[i - 1] == s2[j - 1] == s3[i + j - 1]:\n",
    "                    dp[i][j] = (dp[i - 1][j] | dp[i][j - 1])\n",
    "                elif s1[i - 1] == s3[i + j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "                elif s2[j - 1] == s3[i + j - 1]:\n",
    "                    dp[i][j] = dp[i][j - 1]\n",
    "        return dp[n1][n2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1, n2, n3 = len(s1), len(s2), len(s3)\n",
    "        if n1 + n2 != n3: return False\n",
    "        dp = [[False] * (n2 + 1) for _ in range(n1 + 1)]\n",
    "        dp[0][0] = True\n",
    "        # 赋初值，第一列表示当s2为空时s1与s3是否匹配\n",
    "        for i in range(1, n1 + 1):\n",
    "            if s1[i - 1] == s3[i - 1]:\n",
    "                dp[i][0] = dp[i - 1][0]\n",
    "        # 赋初值，第一排表示当s1为空时s2与s3是否匹配\n",
    "        for j in range(1, n2 + 1):\n",
    "            if s2[j - 1] ==s3[j - 1]:\n",
    "                dp[0][j] = dp[0][j - 1]\n",
    "        for i in range(1, n1 + 1):\n",
    "            for j in range(1, n2 + 1):\n",
    "                if s1[i - 1] == s2[j - 1] == s3[i + j - 1]:\n",
    "                    dp[i][j] = (dp[i - 1][j] | dp[i][j - 1])\n",
    "                elif s1[i - 1] == s3[i + j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "                elif s2[j - 1] == s3[i + j - 1]:\n",
    "                    dp[i][j] = dp[i][j - 1]\n",
    "        return dp[n1][n2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n = len(s1)\n",
    "        m = len(s2)\n",
    "        if m+n != len(s3):\n",
    "            return False\n",
    "        dp = [[True]*(m+1) for _ in range(n+1)]\n",
    "        for i in range(1, m+1):\n",
    "            dp[0][i] = dp[0][i-1] & (s2[i-1] == s3[i-1])\n",
    "        for i in range(1, n+1):\n",
    "            dp[i][0] = dp[i-1][0] & (s1[i-1] == s3[i-1])\n",
    "            for j in range(1, m+1):\n",
    "                dp[i][j] = (dp[i-1][j] & (s1[i-1]==s3[i+j-1])) | (dp[i][j-1] & (s2[j-1] == s3[i+j-1]))\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1, n2, n3 = len(s1), len(s2), len(s3)\n",
    "        if n1 + n2 != n3:\n",
    "            return False\n",
    "        \n",
    "        dp = [[0 for _ in range(n1+1)] for _ in range(n2+1)]\n",
    "        dp[0][0] = 1\n",
    "        # 这里需要注意，s3[i-1]，s3[n-1]会出现数组越界的问题\n",
    "        for i in range(1,n1+1):\n",
    "            if dp[0][i-1] and s1[i-1] == s3[i-1]:\n",
    "                dp[0][i] = 1\n",
    "        \n",
    "        for i in range(1,n2+1):\n",
    "            if dp[i-1][0] and s2[i-1] == s3[i-1]:\n",
    "                dp[i][0] = 1\n",
    "\n",
    "        for i in range(1,n2+1):\n",
    "            for j in range(1,n1+1):\n",
    "                n = i + j\n",
    "                # 这里需要注意,s3[n-1]会出现数组越界的问题, 因此要增加n <= n3的判断\n",
    "                if n <= n3:\n",
    "                    # if dp[i-1][j-1] and (s3[n-2:n] == s1[j-1] + s2[i-1] or s3[n-2:n] == s2[i-1] + s1[j-1]):\n",
    "                    #     dp[i][j] = 1\n",
    "                    if dp[i-1][j] and s3[n-1] == s2[i-1]:\n",
    "                        dp[i][j] = 1\n",
    "                    if dp[i][j-1] and s3[n-1] == s1[j-1]:\n",
    "                        dp[i][j] = 1\n",
    "                else:\n",
    "                    break\n",
    "        return dp[n2][n1] == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        m, n = len(s1) + 1, len(s2) + 1\n",
    "        if m + n - 2 != len(s3): return False\n",
    "        dp = [[False] * n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "\n",
    "        for i in range(1, m):\n",
    "            dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]\n",
    "        for j in range(1, n):\n",
    "            dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i - 1][j] and s1[i - 1] == s3[i + j - 1] or dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]\n",
    "        \n",
    "\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # m, n = len(s1), len(s2)\n",
    "        # if len(s3) != m + n: return False\n",
    "        # dp = [[False] * (n + 1) for _ in range(m + 1)]\n",
    "        # dp[0][0] = True\n",
    "        # for i in range(1, m + 1):\n",
    "        #     dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]\n",
    "        \n",
    "        # for j in range(1, n + 1):\n",
    "        #     dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]\n",
    "        \n",
    "        # for i in range(1, m + 1):\n",
    "        #     for j in range(1, n + 1):\n",
    "        #         dp[i][j] = dp[i - 1][j] and s1[i - 1] == s3[i + j - 1] or dp[i][j - 1] and s2[ j - 1] == s3[i + j - 1]\n",
    "        \n",
    "        # return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        m, n = len(s1), len(s2)\n",
    "        if len(s3) != m + n: return False\n",
    "        dp = [[False] * (n + 1) for _ in range(m + 1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, m + 1):\n",
    "            dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]\n",
    "        \n",
    "        for j in range(1, n + 1):\n",
    "            dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]\n",
    "        \n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = dp[i - 1][j] and s1[i - 1] == s3[i + j - 1] or dp[i][j - 1] and s2[ j - 1] == s3[i + j - 1]\n",
    "        \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        lens1=len(s1)\n",
    "        lens2=len(s2)\n",
    "        f=[[False]*(lens2+1) for _ in range(lens1+1)]\n",
    "        if len(s1)+len(s2)!=len(s3):\n",
    "            return False\n",
    "        f[0][0]=True\n",
    "        for i in range(1,lens1+1):\n",
    "            f[i][0]=(f[i-1][0] and s3[i-1]==s1[i-1])\n",
    "        for i in range(1,lens2+1):\n",
    "            f[0][i]=(f[0][i-1] and s3[i-1]==s2[i-1])\n",
    "        for i in range(1,lens1+1):\n",
    "            for j in range(1,lens2+1):\n",
    "                p=i+j-1\n",
    "                if s2[j-1]==s3[p]:\n",
    "                    f[i][j]=f[i][j] or f[i][j-1]\n",
    "                if s1[i-1]==s3[p]:\n",
    "                    f[i][j]=f[i][j] or f[i-1][j]\n",
    "        return f[-1][-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1, n2, n3 = len(s1), len(s2), len(s3)\n",
    "        if n1 + n2 < n3:\n",
    "            return False\n",
    "        \n",
    "        dp = [[0 for _ in range(n1+1)] for _ in range(n2+1)]\n",
    "        dp[0][0] = 1\n",
    "        # 这里需要注意，s3[i-1]，s3[n-1]会出现数组越界的问题\n",
    "        for i in range(1,min(n1,n3)+1):\n",
    "            if dp[0][i-1] and s1[i-1] == s3[i-1]:\n",
    "                dp[0][i] = 1\n",
    "        \n",
    "        for i in range(1,min(n2,n3)+1):\n",
    "            if dp[i-1][0] and s2[i-1] == s3[i-1]:\n",
    "                dp[i][0] = 1\n",
    "\n",
    "        for i in range(1,n2+1):\n",
    "            for j in range(1,n1+1):\n",
    "                n = i + j\n",
    "                # 这里需要注意,s3[n-1]会出现数组越界的问题, 因此要增加n <= n3的判断\n",
    "                if n <= n3:\n",
    "                    # if dp[i-1][j-1] and (s3[n-2:n] == s1[j-1] + s2[i-1] or s3[n-2:n] == s2[i-1] + s1[j-1]):\n",
    "                    #     dp[i][j] = 1\n",
    "                    if dp[i-1][j] and s3[n-1] == s2[i-1]:\n",
    "                        dp[i][j] = 1\n",
    "                    if dp[i][j-1] and s3[n-1] == s1[j-1]:\n",
    "                        dp[i][j] = 1\n",
    "                else:\n",
    "                    break\n",
    "        return dp[n2][n1] == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        if len(s1)+len(s2)!=len(s3):return False\n",
    "        dp = [[False] * (len(s1)+1) for _ in range(len(s2)+1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, len(s1)+1):\n",
    "            if dp[0][i-1] and s1[i-1]==s3[i-1]:dp[0][i]=True\n",
    "        for i in range(1, len(s2)+1):\n",
    "            if dp[i-1][0] and s2[i-1]==s3[i-1]:dp[i][0]=True\n",
    "        for i in range(2, len(s3)+1):\n",
    "            for index1 in range(1, i):\n",
    "                index2 = i - index1\n",
    "                if index1 > len(s1) or index2>len(s2):continue\n",
    "                # if (s1[index1-1] == s3[i-1] or s2[index2-1] == s3[i-1]) and (dp[index2][index1-1] or dp[index2-1][index1]):dp[index2][index1] = True\n",
    "                if (s1[index1-1] == s3[i-1] and dp[index2][index1-1]) or (s2[index2-1] == s3[i-1] and dp[index2-1][index1]):dp[index2][index1] = True\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        l1 = len(s1)\n",
    "        l2 = len(s2)\n",
    "        if l1+l2!=len(s3): return False\n",
    "        dp = [[False]*(l2+1) for _ in range(l1+1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1,l1+1):\n",
    "            dp[i][0] = s1[i-1]==s3[i-1]\n",
    "            if not dp[i][0]:\n",
    "                break\n",
    "        for j in range(1,l2+1):\n",
    "            dp[0][j] = s2[j-1]==s3[j-1]\n",
    "            if not dp[0][j]:\n",
    "                break\n",
    "        for i in range(1,l1+1):\n",
    "            for j in range(1,l2+1):\n",
    "                dp[i][j] = (dp[i-1][j] and s1[i-1]==s3[i+j-1]) or (dp[i][j-1] and s2[j-1]==s3[i+j-1])\n",
    "        print(dp)\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        m, n, k = len(s1), len(s2), len(s3)\n",
    "        if m + n != k:\n",
    "            return False \n",
    "        \n",
    "        dp = [[False] * (n+1) for _ in range(m+1)]\n",
    "        dp[0][0] = True \n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            dp[i][0] = (dp[i-1][0] and s1[i-1] == s3[i-1])\n",
    "        for i in range(1, n+1):\n",
    "            dp[0][i] = (dp[0][i-1] and s2[i-1] == s3[i-1])\n",
    "        \n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = (dp[i][j-1] and s2[j-1] == s3[i+j-1]) or (dp[i-1][j] and s1[i-1] == s3[i+j-1])\n",
    "        \n",
    "        return dp[m][n]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        # dp[i][j] s1的前i个字符和s2的前j个字符是否可以组成s3的前(i+j)个字符\n",
    "        n1, n2, n3 = len(s1), len(s2), len(s3)\n",
    "        if n1+n2!=n3:\n",
    "            return False\n",
    "            \n",
    "        dp = [[False]*(n2+1) for _ in range(n1+1)]\n",
    "\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, n1+1):\n",
    "            if s1[i-1]==s3[i-1]:\n",
    "                dp[i][0] |= dp[i-1][0]\n",
    "        for j in range(1, n2+1):\n",
    "            if s2[j-1]==s3[j-1]:\n",
    "                dp[0][j] |= dp[0][j-1]\n",
    "        print(dp)\n",
    "        for i in range(1, n1+1):\n",
    "            for j in range(1, n2+1):\n",
    "                if s1[i-1]==s3[i+j-1]:\n",
    "                    dp[i][j] |= dp[i-1][j]\n",
    "                if s2[j-1]==s3[i+j-1]:\n",
    "                    dp[i][j] |= dp[i][j-1]\n",
    "\n",
    "        return dp[n1][n2]      \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        if len(s1) + len(s2) != len(s3):\n",
    "            return False\n",
    "        \n",
    "        from collections import defaultdict\n",
    "        left_cnter = defaultdict(lambda: 0)\n",
    "        right_cnter = defaultdict(lambda: 0)\n",
    "        for item in s1 + s2:\n",
    "            left_cnter[item] += 1\n",
    "        for item in s3:\n",
    "            right_cnter[item] += 1\n",
    "        \n",
    "        if left_cnter != right_cnter:\n",
    "            return False\n",
    "\n",
    "        m = len(s1)\n",
    "        n = len(s2)\n",
    "\n",
    "        result = [[False] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(m + 1):\n",
    "            for j in range(n + 1):\n",
    "                if i == 0:\n",
    "                    if s2[: j] == s3[: i + j]:\n",
    "                        result[i][j] = True\n",
    "                elif j == 0:\n",
    "                    if s1[: i] == s3[: i + j]:\n",
    "                        result[i][j] = True\n",
    "                else:\n",
    "                    flag = False\n",
    "                    if s1[i - 1] == s3[i + j - 1]:\n",
    "                        flag = flag or result[i - 1][j]\n",
    "                    if s2[j - 1] == s3[i + j - 1]:\n",
    "                        flag = flag or result[i][j - 1]\n",
    "                    result[i][j] = flag\n",
    "        return result[m][n]\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        self.len1 = len(s1)\n",
    "        self.len2 = len(s2)\n",
    "        self.len3 = len(s3)\n",
    "        if self.len1+self.len2!=self.len3:\n",
    "            return False\n",
    "        elif self.len1+self.len2+self.len3==0:\n",
    "            return True\n",
    "        elif self.len1==0:\n",
    "            return s2==s3\n",
    "        elif self.len2==0:\n",
    "            return s1==s3\n",
    "        dp = [[False for _ in range(self.len2+1)] for _ in range(self.len1+1)]\n",
    "        dp[0][0]=True\n",
    "        for i in range(1,self.len1+1):\n",
    "            dp[i][0] = (s1[:i]==s3[:i])\n",
    "        for j in range(1, self.len2+1):\n",
    "            dp[0][j] = (s2[:j]==s3[:j])\n",
    "        for i in range(1,self.len1+1):\n",
    "            for j in range(1, self.len2+1):\n",
    "                if s3[i+j-1]==s1[i-1] and s3[i+j-1]==s2[j-1]:\n",
    "                    dp[i][j] = (dp[i-1][j] or dp[i][j-1])\n",
    "                elif s3[i+j-1]==s1[i-1]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                elif s3[i+j-1]==s2[j-1]:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                else:\n",
    "                    dp[i][j]=False\n",
    "        print(dp)\n",
    "        return (dp[-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        if Counter(s3)!=Counter(s1)+Counter(s2):\n",
    "            return False\n",
    "        @lru_cache(None)\n",
    "        def DFS(a,b,c):\n",
    "            if a+b==c or b+a==c:\n",
    "                return True\n",
    "            if (not a or not b) and a+b!=c:\n",
    "                return False\n",
    "            if a[0]!=b[0]:\n",
    "                if a[0]==c[0]:\n",
    "                    return DFS(a[1:],b,c[1:])\n",
    "                elif b[0]==c[0]:\n",
    "                    return DFS(a,b[1:],c[1:])\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if c[0]==a[0]:\n",
    "                    return DFS(a[1:],b,c[1:]) or DFS(a,b[1:],c[1:])\n",
    "                else:\n",
    "                    return False\n",
    "        return DFS(s1,s2,s3)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.visited = []\n",
    "        self.bool = False\n",
    "\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        i, j, x = 0, 0, 0\n",
    "        if len(s1) + len(s2) > len(s3):\n",
    "            return False\n",
    "        self.dfs(i, j, x, s1, s2, s3)\n",
    "\n",
    "        return self.bool\n",
    "\n",
    "    def dfs(self, i, j, x, s1, s2, s3):\n",
    "        if (i,j,x) in self.visited:\n",
    "            return\n",
    "        if x == len(s3) and i == len(s1) and j == len(s2):\n",
    "            self.bool = True\n",
    "            return\n",
    "        self.visited.append((i, j, x))\n",
    "        if i <= len(s1) - 1:\n",
    "            if s1[i] == s3[x]:\n",
    "                self.dfs(i + 1, j, x + 1, s1, s2, s3)\n",
    "        \n",
    "        if j <= len(s2) - 1:\n",
    "            if s2[j] == s3[x]:\n",
    "                self.dfs(i, j + 1, x + 1, s1, s2, s3)\n",
    "        \n",
    "       \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.visited = []\n",
    "        self.bool = False\n",
    "\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        i, j, x = 0, 0, 0\n",
    "        if len(s1) + len(s2) != len(s3):\n",
    "            return False\n",
    "        self.dfs(i, j, x, s1, s2, s3)\n",
    "\n",
    "        return self.bool\n",
    "\n",
    "    def dfs(self, i, j, x, s1, s2, s3):\n",
    "        if (i,j,x) in self.visited:\n",
    "            return\n",
    "        if x == len(s3) and i == len(s1) and j == len(s2):\n",
    "            self.bool = True\n",
    "            return\n",
    "        self.visited.append((i, j, x))\n",
    "        if i <= len(s1) - 1:\n",
    "            if s1[i] == s3[x]:\n",
    "                self.dfs(i + 1, j, x + 1, s1, s2, s3)\n",
    "        \n",
    "        if j <= len(s2) - 1:\n",
    "            if s2[j] == s3[x]:\n",
    "                self.dfs(i, j + 1, x + 1, s1, s2, s3)\n",
    "        \n",
    "       \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n, m = len(s1), len(s2)\n",
    "        if n + m != len(s3): \n",
    "            return False\n",
    "        dp = {}\n",
    "        \n",
    "        # bound         初始化 -1 行 -1列 ~\n",
    "        dp[(-1, -1)] = True\n",
    "        for i in range(n):\n",
    "            if s1[i] == s3[i]:\n",
    "                dp[(i, -1)] = dp[(i-1, -1)]\n",
    "            else:\n",
    "                dp[(i, -1)] = False\n",
    "        \n",
    "        for i in range(m):\n",
    "            if s2[i] == s3[i]:\n",
    "                dp[(-1, i)] = dp[(-1, i-1)]\n",
    "            else:\n",
    "                dp[(-1, i)] = False\n",
    "\n",
    "        # iteration\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if s1[i] == s2[j] == s3[i+j+1]:\n",
    "                    dp[(i, j)] = dp[(i-1, j)] or dp[(i, j-1)]\n",
    "                elif s1[i] == s3[i+j+1]:\n",
    "                    dp[(i, j)] = dp[(i-1, j)]\n",
    "                elif s2[j] == s3[i+j+1]:\n",
    "                    dp[(i, j)] = dp[(i, j-1)]\n",
    "                else:\n",
    "                    dp[(i, j)] = False\n",
    "        \n",
    "        return dp[(n-1, m-1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1, n2, n3 = len(s1), len(s2), len(s3)\n",
    "        if n1 + n2 < n3:\n",
    "            return False\n",
    "        \n",
    "        dp = [[\"\" for _ in range(n1+1)] for _ in range(n2+1)]\n",
    "\n",
    "        for i in range(1,n1+1):\n",
    "            if dp[0][i-1] + s1[i-1] == s3[:i]:\n",
    "                dp[0][i] = s3[:i]\n",
    "        \n",
    "        for i in range(1,n2+1):\n",
    "            if dp[i-1][0] + s2[i-1] == s3[:i]:\n",
    "                dp[i][0] = s3[:i]\n",
    "\n",
    "        for i in range(1,n2+1):\n",
    "            for j in range(1,n1+1):\n",
    "                n = i + j\n",
    "                res = []\n",
    "                # 当dp[i-1][j-1],dp[i-1][j],dp[i][j-1]为真的时候\n",
    "                if (i == 1 and j == 1) or dp[i-1][j-1] != \"\":\n",
    "                    res.append(dp[i-1][j-1] + s1[j-1] + s2[i-1])\n",
    "                    res.append(dp[i-1][j-1] + s2[i-1] + s1[j-1])\n",
    "                if dp[i-1][j] != \"\":\n",
    "                    res.append(dp[i-1][j] + s2[i-1])\n",
    "                if dp[i][j-1] != \"\":\n",
    "                    res.append(dp[i][j-1] + s1[j-1])\n",
    "                if s3[:n] in res: \n",
    "                    dp[i][j] = s3[:n]\n",
    "        return dp[n2][n1] == s3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        length1 = len(s1)\n",
    "        length2 = len(s2)\n",
    "        length3 = len(s3)\n",
    "        if length1 + length2 != length3:\n",
    "            return False\n",
    "            \n",
    "        self.ans = False\n",
    "        # dfs(i, j, k)的含义是s1的第i个字符与s2的第j个字符来构造当前的s3字符的第k个字符\n",
    "        @cache\n",
    "        def dfs(i, j, k):\n",
    "            if self.ans is True:\n",
    "                return\n",
    "            # 边界条件\n",
    "            if i == length1 or j == length2:\n",
    "                if i == length1:\n",
    "                    self.ans = True if s3[k:] == s2[j:] else False\n",
    "                if j == length2:\n",
    "                    self.ans = True if s3[k:] == s1[i:] else False\n",
    "                return\n",
    "            # 如果当前两个值都不能满足与s3中的字符串相符，则直接停止\n",
    "            if s1[i] != s3[k] and s2[j] != s3[k]:\n",
    "                return\n",
    "\n",
    "            if s1[i] == s3[k]:\n",
    "                dfs(i + 1, j, k + 1)\n",
    "            if s2[j] == s3[k]:\n",
    "                dfs(i, j + 1, k + 1)    \n",
    "\n",
    "        dfs(0, 0, 0)       \n",
    "\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1, n2, n3 = len(s1), len(s2), len(s3)\n",
    "        if n1 + n2 < n3:\n",
    "            return False\n",
    "        \n",
    "        dp = [[\"\" for _ in range(n1+1)] for _ in range(n2+1)]\n",
    "\n",
    "        for i in range(1,n1+1):\n",
    "            if dp[0][i-1] + s1[i-1] == s3[:i]:\n",
    "                dp[0][i] = s3[:i]\n",
    "        \n",
    "        for i in range(1,n2+1):\n",
    "            if dp[i-1][0] + s2[i-1] == s3[:i]:\n",
    "                dp[i][0] = s3[:i]\n",
    "\n",
    "        for i in range(1,n2+1):\n",
    "            for j in range(1,n1+1):\n",
    "                n = i + j\n",
    "                if (i == 1 and j == 1) or dp[i-1][j-1] != \"\":\n",
    "                    if s3[:n] == dp[i-1][j-1] + s1[j-1] + s2[i-1] or s3[:n] == dp[i-1][j-1] + s2[i-1] + s1[j-1]:\n",
    "                        dp[i][j] = s3[:n]\n",
    "                        continue\n",
    "                if dp[i-1][j] != \"\" and s3[:n] == dp[i-1][j] + s2[i-1]:\n",
    "                    dp[i][j] = s3[:n]\n",
    "                    continue\n",
    "                if dp[i][j-1] != \"\" and s3[:n] == dp[i][j-1] + s1[j-1]:\n",
    "                    dp[i][j] = s3[:n]\n",
    "                    continue\n",
    "        return True if dp[n2][n1] == s3 else False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "       @cache\n",
    "       def dfs(i: int, j: int, k: int) -> bool:\n",
    "          if k == n3:\n",
    "             return True\n",
    "          if i == n1:\n",
    "             return s2[j:] == s3[k:]\n",
    "          if j == n2:\n",
    "             return s1[i:] == s3[k:]\n",
    "          res = False\n",
    "          if s1[i] == s3[k]:\n",
    "             res = res or dfs(i + 1, j, k + 1)\n",
    "          if s2[j] == s3[k]:\n",
    "             res = res or dfs(i, j + 1, k + 1)\n",
    "          return res\n",
    "          \n",
    "       n1 = len(s1)\n",
    "       n2 = len(s2)\n",
    "       n3 = len(s3)\n",
    "       if n1 + n2 != n3:\n",
    "          return False\n",
    "       return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        l1, l2, l3 = len(s1), len(s2), len(s3)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j, k):\n",
    "            if i == l3:\n",
    "                return j == l1 and k == l2\n",
    "            ss1 = s1[j] if j < l1 else '0'\n",
    "            ss2 = s2[k] if k < l2 else '0'\n",
    "            ss3 = s3[i]\n",
    "            if ss1 == ss2 == ss3:\n",
    "                return dfs(i + 1, j + 1, k) or dfs(i + 1, j, k + 1)\n",
    "            elif ss3 == ss1 and ss3 != ss2:\n",
    "                return dfs(i + 1, j + 1, k)\n",
    "            elif ss3 == ss2 and ss3 != ss1:\n",
    "                return dfs(i + 1, j, k + 1)\n",
    "            else:\n",
    "                return False\n",
    "        return dfs(0, 0, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:\n",
    "        n1, n2, n3 = len(s1), len(s2), len(s3)\n",
    "        if n1 + n2 < n3:\n",
    "            return False\n",
    "        \n",
    "        dp = [[\"\" for _ in range(n1+1)] for _ in range(n2+1)]\n",
    "\n",
    "        for i in range(1,n1+1):\n",
    "            if dp[0][i-1] + s1[i-1] == s3[:i]:\n",
    "                dp[0][i] = s3[:i]\n",
    "        \n",
    "        for i in range(1,n2+1):\n",
    "            if dp[i-1][0] + s2[i-1] == s3[:i]:\n",
    "                dp[i][0] = s3[:i]\n",
    "\n",
    "        for i in range(1,n2+1):\n",
    "            for j in range(1,n1+1):\n",
    "                n = i + j\n",
    "                res = []\n",
    "                # 当dp[i-1][j-1],dp[i-1][j],dp[i][j-1]为真的时候\n",
    "                if (i == 1 and j == 1) or dp[i-1][j-1] != \"\":\n",
    "                    res.append(dp[i-1][j-1] + s1[j-1] + s2[i-1])\n",
    "                    res.append(dp[i-1][j-1] + s2[i-1] + s1[j-1])\n",
    "                if dp[i-1][j] != \"\":\n",
    "                    res.append(dp[i-1][j] + s2[i-1])\n",
    "                if dp[i][j-1] != \"\":\n",
    "                    res.append(dp[i][j-1] + s1[j-1])\n",
    "                if s3[:n] in res: \n",
    "                    dp[i][j] = s3[:n]\n",
    "        return True if dp[n2][n1] == s3 else False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
